package com.cty.A_GeneralDataStructures.A_Array.Array;

import com.cty.F_common.DataItem;

/**
 * @Auther: cty
 * @Date: 2020/6/13 15:52
 * @Description:  无序数组
 * 应用场景：
 *      当数据量少时，考虑数组或链表
 *          当数据量可预测或内存充足时，考虑数组
 *              当插入比查找重要时，考虑无序数组
 * 重要操作：
 *      ① find(long): DataItem    O(N)
 *      ② insert(DataItem): boolean    O(1)
 *      ③ delete(long): DataItem    O(N)
 * @version: 1.0
 */
public class Array {
    private int maxSize;
    private DataItem[] array;
    private int nItems;

    public Array(int maxSize){
        this.maxSize = maxSize;
        array = new DataItem[maxSize];
        nItems = 0;
    }

    public boolean isEmpty(){
        return (nItems == 0);
    }

    public boolean isFull(){
        return (nItems == maxSize);
    }

    public int size(){
        return nItems;
    }

    public void displayArray(){
        for(int i = 0; i< nItems; i++)
            System.out.print(array[i].getKey() + " ");
        System.out.println();
    }

    /**
     * 查找  O(N)
     * @param key
     * @return
     */
    public DataItem find(long key){
        for(int i = 0; i< nItems; i++)
            if(array[i].getKey() == key)
                return array[i];
        return null;
    }  // end find()

    /**
     * 插入  O(1)
     * @param item
     * @return
     */
    public boolean insert(DataItem item){
        if(isFull())
            return false;

        array[nItems++] = item;
        return true;
    }  // end insert()

    /**
     * 删除  O(N)
     * @param key
     * @return
     */
    public DataItem delete(long key){
        if(isEmpty())
            return null;

        int i;
        for(i=0; i< nItems; i++)
            if(array[i].getKey() == key)
                break;
        if(i == nItems)
            return null;

        DataItem temp = array[i];
        for(int j = i; j< nItems -1; j++)
            array[j] = array[j+1];
        nItems--;
        return temp;
    }  // end delete()

}  // end Array{}
